package fun.codedesign.jdk.math.algorithm.sort;

/**
 * 计数排序 <br>
 * <pre>
 *     计数排序的注意点在于优化的反向填充稳定排序，以及最小数组大小的控制
 *     计数排序对于大规模的固定范围的数据能有很好的排序效果
 * </pre>
 *
 * @author zengjian
 * @create 2018-06-26 17:26
 * @since 1.0.0
 */
public class CountSorter implements Sorter {

    @Override
    public void sort(int[] arr) {
        int min = arr[0];
        int max = min;
        int length = arr.length;
        // 找出数组中的最小值以及最大值
        for (int i = 0; i < length; i++) {
            min = Math.min(min, arr[i]);
            max = Math.max(max, arr[i]);
        }
        // 新建一个用来索引的数组
        int countLength = max - min + 1;
        int[] count = new int[countLength];
        // 循环一趟记录下所有数值(最大值与当前值之差)的个数
        for (int i = 0; i < length; i++) {
            count[arr[i]-min] += 1;
        }
        // 准备好排序后的索引
        for (int i = 0; i < countLength - 1; i++) {
            count[i + 1] += count[i];
        }
        // 反向填充
        int[] newArr = new int[length];
        for (int i = length - 1; i >= 0; i--) {
            // 此处需要-1处理，因为初始值为1开始，其次下一次同样的值需要一个更小的索引
            newArr[--(count[arr[i]-min])] = arr[i];
        }
        // TODO 引用的问题
        for (int i = 0; i < length; i++) {
            arr[i] = newArr[i];
        }
    }
}
